Many applications require the computation of a remainder when a dividend m is divided by a divisor n. The general case of any arbitrary numerator (dividend) and arbitrary denominator (divisor) may require actual division computation which may be a computationally expensive operation.
For a specific class of divisor values, there are methods available in literature that enable a reduced complexity implementation of the remainder computation. For example, if the divisor n is a power of two, the remainder of m/n operation can be obtained by simply using the lowest log2(n) bits of the dividend m. However, there is no general method to efficiently compute a remainder for different divisor values. Cunningham numbers are a simple type of binomial numbers of the form bk±1 where b and k are integers and b is not already a power of some other number. In some applications a class of Cunningham numbers is used for the purpose of randomization. An example of this is the 3rd Generation Partnership Project (3GPP) Long term Evolution (LTE) wireless communication system. In 3GPP LTE wireless communication system, a client terminal needs to search for the resource assignment messages from a wireless communication network. This search involves remainder computation with the divisor being a Cunningham number. Specifically, a client terminal is required to perform the following operation:Yk=(A*Yk-1)mod D  (EQ. 1)where A=39827, D=65537 and k ranges from 0 to 9 with Yk-1 initialized to some non-zero value. By definition the parameter Yk is constrained to be within 16 bits. The divisor D in this case is a member of a class of Cunningham numbers, i.e., D=65537=216+1. A method and apparatus are disclosed that enable low complexity implementation of remainder computation when the divisor is a class of Cunningham numbers.